Conventionally, an image processing apparatus based on predictive coding is known. The predictive coding is realized with a sequence conversion unit to convert image data to prediction errors by predictive conversion, and an entropy coding unit to convert the prediction errors outputted from the sequence conversion unit to coded data with reduced redundancy by entropy coding such as Huffman coding.
As the characteristic of prediction-error occurrence frequency differs in accordance with the image, it is desirable to improve coding efficiency in order to perform optimum entropy coding on each image.
As a method for realizing optimum entropy coding on each image, 2-pass coding processing is known. In this method, the characteristic of prediction-error occurrence frequency is examined in the first pass, then an entropy coding method is determined based on the characteristics, and actual coding is performed in the second pass.
However, the above method is not frequently employed for various reasons such as the complexity of processing, the increment in memory capacity, and the load of code amount for separate transmission of information on entropy coding methods. Generally, the entropy coding method is determined in accordance with the characteristics of a general prediction error sequence.
In this case, the characteristic of prediction-error occurrence frequency is examined by previously encoding several images, and a coding method is determined based on the characteristics.
FIG. 6 shows an example of the above-described conventional image processing apparatus. In FIG. 6, reference numeral 201 denotes a buffer; 202, a predictor; 206, a subtracter; 204, a memory; 205, a Huffman encoder; and 111 and 112, signal lines. FIG. 2 shows an example of the image processing apparatus which employs predictive conversion using neighboring pixels for sequence conversion in order to convert image data to prediction errors, and employs Huffman coding as the coding processing.
In FIG. 2, prior to actual encoding, the prediction error frequency distribution, obtained by previously sequence-converting image data indicating several images, is examined, and a Huffman table is generated in correspondence with the prediction error frequency distribution, and the table is stored into the memory 204. As a general characteristic of prediction error frequency distribution, the occurrence frequency is high around a prediction error “0”, and the occurrence frequency becomes gradually lower as the prediction error absolute value increases. Accordingly, in the Huffman code stored in the memory 204, a short code word is allocated around the prediction error “0”, while a long code word is allocated to a high prediction error absolute value.
First, image data is sequentially inputted from the signal line 206. The buffer 201 holds the image data inputted from the signal line 206 by two lines. The predictor 202 reads image data of a pixel a immediately preceding a coding subject pixel and 1-line previous pixel b from the buffer 201, and performs calculation p=(a+b)/2, thereby generating a predicted value p.
The subtracter 203 outputs an error value e between image data x of coding subject pixel and the predicted value p. The Huffman encoder 205 refers to the Huffman table previously stored in the memory 204, and outputs coded data corresponding to the error value e from the signal line 207. Generally, the occurrence frequency of the prediction error e is high around the value “0” while it becomes lower as the value becomes away from “0”. Accordingly, as shown in FIG. 8, a Huffman table where a short code word is allocated to prediction errors around “0”, while a long code word is allocated to prediction errors away from “0”, is employed.
When a natural image, especially, a picture image (obtained by reading a photograph with an image scanner or image sensing by a digital camera) is encoded, as adjacent pixels have approximately the same pixel value, the probability is high that the error between predicted value and real pixel value is “0” or nearly “0”. Accordingly, the efficiency of compression coding is high. However, when image data having discrete pixel values such as a CG image or a limited color image is encoded by the above-described conventional image processing apparatus, the prediction-error occurrence frequency upon the above sequence conversion may be discrete.
In such case, a prediction error, which almost does not occur or does not occur at all, exists, even though a short code length is allocated by entropy encoding. Thus, the compressibility cannot be improved.
Regarding such problem, conventionally known are an entropy coding method of determining whether or not the prediction-error occurrence frequency is discrete, changing coded data corresponding to the prediction errors based on the result of determination (e.g., Japanese Patent Application Laid-Open No. Hei 10-004551), and a method of determining whether or not a coding subject image is constructed with discrete pixel values and correcting prediction values based on the result of determination (e.g., Japanese Patent Application Laid-Open No. Hei 10-004557). Note that both of above two references has been issued as U.S. Pat. No. 6,028,963.
These methods are used for obtaining effective improvement under constraints of 1-pass encoding. However, there is a need for further improvement in compression efficiency using 2-pass encoding.